package code901_1000.code90_100;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 在给定的网格中，每个单元格可以有以下三个值之一：
 *
 * 值 0 代表空单元格；
 * 值 1 代表新鲜橘子；
 * 值 2 代表腐烂的橘子。
 * 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
 *
 * 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
 *
 * 输入：[[2,1,1],[1,1,0],[0,1,1]]
 * 输出：4
 *
 * 输入：[[2,1,1],[0,1,1],[1,0,1]]
 * 输出：-1
 * 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
 *
 * 输入：[[0,2]]
 * 输出：0
 * 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
 */
public class _994orangesRotting {

    /**
     * 思考，二维数组的广度遍历.
     * 使用广度遍历的方法，已经成功解决单次遍历的计算。但对于本题而言，未考虑两个坏橘子同时腐蚀的情况。
     * 故普通的层序遍历方法走不通！！！
     *
     * 重新思考：第一种方法：对每个腐烂橘子都进行广度优先遍历，最终结果是所有橘子被腐烂的最短时间的最大值。但十分耗时，需选取其他思路
     *
     * 方法二：多源广度优先搜索：观察到对于所有的腐烂橘子，其实它们在广度优先搜索上是等价于同一层的节点的。
     * 假设这些腐烂橘子刚开始是新鲜的，而有一个腐烂橘子(我们令其为超级源点)会在下一秒把这些橘子都变腐烂，
     * 而这个腐烂橘子刚开始在的时间是 -1−1 ，那么按照广度优先搜索的算法，下一分钟也就是第 00 分钟的时候，
     * 这个腐烂橘子会把它们都变成腐烂橘子，然后继续向外拓展，所以其实这些腐烂橘子是同一层的节点。那么在广度优先搜索的时候，
     * 我们将这些腐烂橘子都放进队列里进行广度优先搜索即可，最后每个新鲜橘子被腐烂的最短时间 dis[x][y]dis[x][y]
     * 其实是以这个超级源点的腐烂橘子为起点的广度优先搜索得到的结果。
     *
     * 结果：就是不用判断每一个节点的腐烂情况，初始直接将所有的腐烂节点入队，当作一个超级节点即可。
     * 执行用时：     * 3 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 37.7 MB     * , 在所有 Java 提交中击败了     * 88.13%     * 的用户
     *
     *
     * @param grid
     * @return
     */
    public static int orangesRotting(int[][] grid) {
        int result = 0;
        int[] dx = {1,0,0,-1};
        int[] dy = {0,1,-1,0};
        boolean isOrange;
        Queue<int[]> queue = new LinkedList<>();
        int xLength = grid.length;
        int yLength = grid[0].length;
        for (int i = 0; i < xLength; i++) {
            for (int j = 0; j < yLength; j++) {
                // 如果有腐烂的橘子，进行层序遍历
                if(grid[i][j] == 2){
                    queue.offer(new int[]{i,j});
                }
            }
        }
        // 对这个超级节点执行广度优先遍历即可
        while (!queue.isEmpty()){
            isOrange = false;
            int queueSize = queue.size();
            for (int l = 0; l < queueSize; l++) {
                int[] now = queue.poll();
                for (int k = 0; k < 4; k++) {
                    int nowX = now[0] + dx[k];
                    int nowY = now[1] + dy[k];
                    if(nowX>=0&&nowY>=0&&nowX<xLength&&nowY<yLength){
                        // 只要有橘子就得遍历
                        if(grid[nowX][nowY]==1){
                            isOrange = true;
                            queue.offer(new int[]{nowX,nowY});
                            grid[nowX][nowY] = 2;
                        }
                    }
                }
            }
            if(isOrange){
                result += 1;
            }
        }

        // 如果现在还有好橘子，那证明永远也腐蚀不了，返回-1.
        for (int i = 0; i < xLength; i++) {
            for (int j = 0; j < yLength; j++) {
                if(grid[i][j]==1){
                    return -1;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] arr = {{2,1,1},{1,1,1},{0,1,2}};
        System.out.println(orangesRotting(arr));
    }

}
